/*
 *  POJ1080: Human Gene Functions
 */

/*-------- Includes --------*/
#include <iostream>
#include <algorithm>

using namespace std;

/*-------- Defines --------*/
#define INF 1000000000

/*-------- Types --------*/


/*-------- Global Variables --------*/
int  N1, N2;
char s1[101];
char s2[101];

int d[101][101];

int tab['T' + 1]['T' + 1];

/*-------- Function Prototypes --------*/
void init_table();

/*-------- Main Function --------*/
int main(int argc, char const *argv[])
{
    int nCase;

    cin >> nCase;

    init_table();

    while (nCase--) {
        cin >> N1 >> s1;
        cin >> N2 >> s2;

        // initialize
        d[0][0] = 0;

        for (int i = 1; i <= N1; i++) d[i][0] = d[i-1][0] + tab[s1[i-1]]['-'];
        for (int i = 1; i <= N2; i++) d[0][i] = d[0][i-1] + tab['-'][s2[i-1]];

        for (int i = 1; i <= N1; i++) {
            for (int j = 1; j <= N2; j++) {
                d[i][j] = d[i-1][j-1] + tab[s1[i-1]][s2[j-1]];

                d[i][j] = max(d[i][j], d[i-1][j] + tab[s1[i-1]]['-']);
                d[i][j] = max(d[i][j], d[i][j-1] + tab['-'][s2[j-1]]);
            }
        }

        cout << d[N1][N2] << endl;
    }
}

/*-------- Functions --------*/
void init_table()
{
    tab['A']['A'] = 5;
    tab['C']['C'] = 5;
    tab['G']['G'] = 5;
    tab['T']['T'] = 5;
    tab['-']['-'] = -INF;
    tab['A']['C'] = tab['C']['A'] = -1;
    tab['A']['G'] = tab['G']['A'] = -2;
    tab['A']['T'] = tab['T']['A'] = -1;
    tab['A']['-'] = tab['-']['A'] = -3;
    tab['C']['G'] = tab['G']['C'] = -3;
    tab['C']['T'] = tab['T']['C'] = -2;
    tab['C']['-'] = tab['-']['C'] = -4;
    tab['G']['T'] = tab['T']['G'] = -2;
    tab['G']['-'] = tab['-']['G'] = -2;
    tab['T']['-'] = tab['-']['T'] = -1;
}
